package sort;

public class MergeSort {
    public int[] sortArray(int[] nums) {
        mergerSort(nums,0,nums.length - 1);
        return nums;
    }

    public int[] mergerSort(int[] nums,int left,int right){
        if(left >= right) return nums;

        int mid = left + (right - left)/2;
        mergerSort(nums,left,mid);
        mergerSort(nums,mid+1,right);
        merge(nums,left,mid,right);
        return nums;
    }

    public void merge(int[] nums,int left,int mid,int right){
        int[] tmp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right) {
            if(nums[i] <= nums[j]){
                tmp[t] = nums[i];
                i++;
                t++;
            }else{
                tmp[t] = nums[j];
                j++;
                t++;
            }
        }
        while (i <= mid){
            tmp[t] = nums[i];
            i++;
            t++;
        }
        while (j <= right){
            tmp[t] = nums[j];
            j++;
            t++;
        }
        for (int k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }
}
